-module(ex08b).
-export([parse/1]).

%% Syntax Grammer
%% expr -> term | term + expr | term - expr
%% term -> factor | factor * term | factor / term
%% factor -> NUM | (expr)

parse(Tokens) ->
    element(1, expr(Tokens)).

expr(Tokens) ->
    {LeftTree, RestTokens} = term(Tokens),
    if 
	length(RestTokens) == 0 -> 
	    {LeftTree, []};
	true -> 
	    [Head | Tail] = RestTokens,
	    {Lt, Rt} = expr(Tail),
	    case Head of
		$+ -> {{plus, LeftTree, Lt}, Rt};
		$- -> {{sub, LeftTree, Lt}, Rt};
		_Other -> {LeftTree, RestTokens}
	    end
    end.

term(Tokens) ->
    {LeftTree, RestTokens} = factor(Tokens),
    if 
	length(RestTokens) == 0 ->
	    {LeftTree, []};
	true -> [Head | Tail] = RestTokens,
		 {LT, Rt} = term(Tail),
		 case Head of
		     $* -> {{multi, LeftTree, LT}, Rt};
		     $/ -> {{divide, LeftTree, LT}, Rt};
		     _Other -> {LeftTree, RestTokens}
		 end
    end.

factor([]) ->
    {{}, []};
factor([Head | Tail]) ->
    if 
	Head >= $0, Head =< $9 -> 
	    {Int, Rest} = string:to_integer([Head | Tail]),
	    {{num, Int}, Rest};
	Head == $( -> 
	    {Lt, Rt} = expr(Tail),
	    is_match(Rt, $)),
	    [_ | T] = Rt,
	    {Lt, T};
	true ->
	    {{}, [Head | Tail]}
    end.

				     
is_match([Token | _], Token) ->
    ok;
is_match(_, _) ->
    throw ({'EXIT', "unexpected token"}).			    
